package lc.q1_50;


import java.io.FileInputStream;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 37. 解数独
 * 编写一个程序，通过已填充的空格来解决数独问题。
 *
 * 一个数独的解法需遵循如下规则：
 *
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 * 空白格用 '.' 表示。
 *
 *
 *
 */
public class Q37 {
    int[][] hs = new int[9][9];
    int[][] vs = new int[9][9];
    int[][] ks = new int[9][9];
    char[][] board;
    boolean solved;

    public void solveSudoku(char[][] board) {
        this.board = board;
        // 数独，每个数在横竖和同一个块九宫格中唯一
        // 先放进一个数，如果下一步没有数可放，那么就回溯、放下一个数
        // 假设对于任意个未填位置，横排能填的数字、竖排能填的数字、和九宫格能填的数字没有交叉，说明数组有数字填错，重来
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                final char c = board[i][j];
                if (c != '.') {
                    placeNumber(i, j, c);
                }
            }
        }
        backtrack(0,0);
    }

    private boolean couldPlaceNum(int row, int col, int c) {
        int num = c - '1';
        return hs[row][num] < 1 && vs[col][num] < 1 && ks[row / 3 * 3 + col / 3][num] < 1;
    }

    private void backtrack(int row, int col) {
        // 回溯
        if (board[row][col] == '.') {
            // 放数
            for (char i = '1'; i <= '9'; i++) {
                // 放数
                if (couldPlaceNum(row, col, i)) {
                    // 放数
                    placeNumber(row, col, i);
                    placeNextNumbers(row, col);
                    if (!solved) {
                        // 撤回，然后放下一个数字
                        remove(row, col, i);
                    }
                }
            }
        } else {
            // 放其他的数
            placeNextNumbers(row,col);
        }
    }

    private void placeNumber(int row, int col, char c) {
        int num = c - '1';
        hs[row][num]++;
        vs[col][num]++;
        final int[] k = ks[row / 3 * 3 + col / 3];
        k[num]++;
        board[row][col] = c;
    }

    // 放置下一行列
    private void placeNextNumbers(int row, int col) {
        if (row == 8 && col == 8) {
            // 已解决
            solved = true;
        } else {
            if (col == 8) {
                backtrack(row + 1, 0);
            } else {
                backtrack(row, col + 1);
            }
        }
    }

    // 移除已填的数字
    private void remove(int row, int col, char c) {
        int num = c - '1';
        hs[row][num]--;
        vs[col][num]--;
        final int[] k = ks[row / 3 * 3 + col / 3];
        k[num]--;
        board[row][col] = '.';
    }

    public static void main(String[] args) throws Exception{
        try (FileInputStream fis = new FileInputStream("Q36_input.txt")) {
            final Scanner scanner = new Scanner(fis);
            scanner.nextLine();
            char[][] chars = new char[9][];
            for (int i = 0; i < 9; i++) {
                final String line = scanner.nextLine();
                // 如何提取所有的字符？
                final String s = line.replaceAll("[^\\d.]", "");
                chars[i] = Arrays.copyOf(s.toCharArray(), 9);
            }
            final Q37 q37 = new Q37();
            q37.solveSudoku(chars);
            for (char[] aChar : chars) {
                for (char c : aChar) {
                    System.out.print(c + "\t");
                }
                System.out.println();
            }
            Q36 q36 = new Q36();
            System.out.println(q36.isValidSudoku(chars));
        }
    }



}
